package algorithm.bitmanipulation;

/**
 * leetcode : https://leetcode.com/problems/single-number/description/
 * Difficulty : Easy
 * 问题： 一个数组中有很多数字是成对出现的，但是其中有一个数字是单独出现的，找出这个单独的数字
 *
 * 利用二进制的 异或运算。
 * 异或运算 1^1=0 0^0=0 1^0-1 0^1=1
 * 也就是说，相同的两个数字异或=0。不同的位数异或会将差异结果保存为1，再次异或就会消除
 *
 * @Author Antony
 * @Since 2018/7/4 12:02
 */
public class OneSingleNum {

    public static void main(String[] args) {
        int[] nums = new int[]{2,4,67,9,435,4,9,435,2,8,67};
        System.out.println(singleNumber(nums));
    }

    /**
     * (beats 100.0% - 0ms)
     */
    public static int singleNumber(int[] nums) {
        int result=nums[0];
        int i=1;
        while(i<nums.length){
            result ^= nums[i++];
        }
        return result;
    }

    public static int searchSingleNum(int[] nums){
        int result = nums[0];
        for(int i=1; i<nums.length; i++){
            result ^= nums[i];
        }

        return result;
    }
}
